A model of a prior art digital communication system is illustrated in FIG. 1. Information source 10 generates either analog or discrete information which the source encoder 11 encodes into an information sequence, x. The channel encoder 12 transforms the information sequence into a new sequence by a process known as channel encoding. Modulator 13 uses the encoded output to generate channel signals for transmission over transmission channel 14 using standard modulation methods such as amplitude, frequency, phase or pulse modulation. In general, transmission channel 14 will exhibit noise and other impairments, e.g. frequency and phase distortion and a variety of fading characteristics. Digital demodulator 15 demodulates the transmitted signal to produce an estimate of the encoded information sequence. Channel decoder 16 then takes this estimate and attempts to reproduce the information sequence using the redundant bits. Finally, source decoder 17 transforms the reconstructed information sequence, x, into a form suitable for information destination 18. See generally, A. M. Michelson & A. H. Levesque, Error Control Techniques for Digital Communications, John Wiley & Sons, New York, 1985.
Channel encoding is a means to efficiently introduce redundancy into a sequence of data to promote the reliability of transmissions. There are at least three ways in which redundant information may be used to improve the accuracy or reliability of the received information: 1) error detection--where the decoder determines only whether the received data sequence is correct or if errors have occurred; 2) error correction--where the decoder uses the redundant information to both detect and correct errors in the received sequence; and 3) automatic repeat request--where the detection of an error will automatically initiate a request for a repeat of the data. More redundancy is required to correct errors than simply to detect errors in an encoded message. Nicholas Maslin, HF Communications: A Systems Approach, Plenum Press, New York, 1987. Two principle techniques employed to introduce redundancy are block coding and convolutional coding. See, e.g., S. Lin & D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1983.
An (n,k) block code takes a block of k information bits and transforms the block into an n bit codeword by adding n-k parity bits in accordance with a prescribed encoding rule. The n bit blocks are then transmitted over the communication channel. The code rate, R, is defined as R=k/n. At the receiver end of the channel, the decoder makes estimates of the original k information bits using the received sequence including the redundancy introduced by the n-k parity bits. Block codes are memoryless in that each n bit codeword output from the decoder depends only on the present k bit information block.
Convolutional codes generally operate on a stream of information bits. The stream is broken into k bit blocks. The information bits are passed into a shift register in blocks of k bits. The stages of the shift register may store v groups of the k bit blocks. The stages are connected to linear algebraic function generators. The outputs of the function generators are then selectively combined to produce the coded output of n bits. Each encoded block depends not only on the present k bit message block input to the shift register but also on the v previous message blocks. Thus, a convolutional code has memory of order v. The code rate, R, of a convolutional code is R=k/n, and the constraint length of the code is v+1. Typically, k and n are small integers and redundancy is added by increasing the length of the shift register. As is well known, the operation of convolutional encoders and decoders can be completely described in terms of either a trellis diagram or a state diagram or table. See Michelson & Levesque, supra.
The Viterbi algorithm (VA) is a well known method for decoding convolutional codes. See A. J. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm," IEEE Trans. Info. Theory, Vol. IT-13, 260-269 (April 1967). The algorithm is also described in detail in G. D. Forney, Jr., "The Viterbi Algorithm," Proc. IEEE, Vol. 61, No. 3, 268-278 (March 1973). The VA is the optimum decoding algorithm in the sense of maximum likelihood estimation for a convolutionally encoded sequence transmitted over a memoryless channel. The basic theoretical concept of the VA can be described as correlating all possible transmitted code sequences with the received sequence and then choosing as the "survivor" the sequence where the correlation is maximum, i.e. the path with the best "metric".
When convolutional codes are used for continuous data transmission, it may be necessary to truncate survivors to manageable window or lengths, .delta. within the decoding trellis. Thus, the VA must come to decision on the best path through the trellis nodes up to the time i-.delta.. However, by framing data into blocks, and terminating the blocks by appending a number of zero bits to the last information bit for the purpose of clearing the shift register, the VA can be used to design a non-systematic block code of length N. In this case, the trellis begins and ends at the known states s.sub.0 =(0 . . . 0) and s.sub.N =(0 . . . 0). The termination at state s.sub.N =(0 . . . 0) is achieved by transmitting v zeros at the end of every information block. Hence, the code rate for blockwise data transmission, R.sub.BL, is given as ##EQU1## where N is the block length, v is the memory, and R is the code rate.
The Viterbi algorithm and the extended Viterbi algorithms described herein are explained for a rate R=1/2 binary convolutional code with four states. Generalization to other codes follows easily. Throughout, the discussion will proceed (without loss of generality) using blocked convolutional codes. The trellis associated with the convolutional code terminates into one known state.
A segment of a trellis for a rate R=1/2 convolutional code with memory v=2 is shown in FIG. 2. Since the code is of memory v=2, there are four possible states, s.sub.i =0,1,2,3 associated with the respective bit patterns, u.sub.1 u.sub.2, 00, 01, 10, and 11. Each of the nodes 30-33 in the trellis corresponds to a distinct state s.sub.i at a given time i, and nodes 34-37 correspond to states at time i+1. Each of the branches 40-47 represents the transition EQU .xi..sub.i =(s.sub.i+1, s.sub.i)
from state s.sub.i to some next state s.sub.i+1 at the next time instant. Every state s.sub.i in the trellis corresponds to the possible content of the encoder shift register at time instant i. The two branches leaving every state correspond to the possible transmitted information bit x.sub.i .epsilon.{0,1}. Upper branches 40-43 indicate a "0" is transmitted; lower branches 44-47 indicate a "1" is transmitted. Therefore, the bits attached to the possible transitions .xi..sub.i =(s.sub.i+1,s.sub.i) are equivalent to the n encoded bits, (u.sub.i1, . . . , u.sub.in) which are generated by shifting from state s.sub.i to s.sub.i+1, i.e. s.sub.i .fwdarw.s.sub.i+1.
At every time instant i+1 and at any state s.sub.i+1, the VA computes the cumulative metrics .GAMMA.(s.sub.i+1,s.sub.i), to that instant EQU .GAMMA.(s.sub.i+1,s.sub.i)=.GAMMA.(s.sub.i)+.lambda.[.xi..sub.i =(s.sub.i+1,s.sub.i)]
for all possible transitions .xi..sub.i =(s.sub.i+1,s.sub.i). .GAMMA.(s.sub.i) is the cumulative metric up to time instant i, and .lambda.[.xi.=(s.sub.i+1,s.sub.i)] is the metric increment for the transition. For the binary code considered in FIG. 2, there are always two paths merging at every state s.sub.i+1. Out of the two possible candidates for the next decoding step, the one with the maximum accumulated metric ##EQU2## is selected, and .GAMMA.(s.sub.i+1) and its corresponding survivor path, x(s.sub.i+1), are stored for further computation. After each decoding step the time parameter i is incremented by one and the computation process is repeated until i=N. At time instant i=N only the maximum likelihood path x, i.e. the path with the best cumulative metric, is left.
Hard decision or soft decision schemes may be employed in determining the best path through the trellis. In a hard decision scheme, the metric may be defined as the Hamming distance between the received word and the codewords. In a soft decision scheme, the Hamming metric is replaced by a soft decision metric, such as by computing the likelihoods of the candidate paths given knowledge of the probability distribution of the received data at the input to the decoder. See generally, J. C. Clark, Jr. & J. B. Cain, Error--Correction Coding for Digital Communications, Plenum Press, New York, 1982; Michelson & Levesque, supra, at 303-305. On the additive Gaussian noise channel, soft decision decoding of the demodulator output results in a performance gain of about 2-3 dB as compared to hard decision decoding. Lin & Costello, supra, at 329; Clark & Cain, supra, at 227.
The maximum likelihood approach and the soft decoding ability of the VA have made the VA useful in a wide range of applications. A convolutional code decoded by the VA in practice is often superior to a block code of equivalent complexity. Besides its applications for channel encoding, the VA can be used for equalizing channels with intersymbol interference. G. D. Forney, Jr., "Maximum Likelihood Sequence Estimation of Digital Signals in the Presence of Intersymbol Interference," IEEE Trans. Info. Theory, Vol. IT-18, No. 3, 363-378 (May 1972). The VA has been used for demodulation of trellis coded modulation, see G. Ungerbock, "Channel Coding with Multilevel Phase/Signals," IEEE Trans. Info. Theory, Vol. IT-28, No. 1, 55-67 (January 1982), as well as for demodulation of partial response continuous phase modulation. See J. B. Anderson, T. Aulin & C-E. Sundberg, Digital Phase Modulation, Plenum Press, New York, 1986. The VA may also be applied to problems in text and pattern recognition. As noted previously, convolutional codes can be used to design non-systematic block codes which can then be decoded optimally by the VA. Thus, the VA is used to advantage not only in decoding convolutional codes but also with a variety of other codes and other transmission techniques, all of which can generally be characterized by a trellis like structure.
Unlike block codes, the maximum likelihood decoder for convolutional codes and other trellis-based structures is complete in that it decodes every received sequence. Thus, decoders for convolutional codes generally lack the ability to signal a warning in the event of potential decoding error. An improvement in the performance of concatenated coding systems (i.e. systems with multiple levels of encoding) could be obtained if the VA, used as the inner decoder, could signal a warning in the event of a potential decoding error to an outer stage of processing. In other words, if the VA could deliver additional information, such as an indicator of the reliability of the decoding, to an outer stage of processing, then the system performance could be improved. This is particularly true where the outer coder is a speech (source) coder. See, e.g., N. Seshadri & C-E. W. Sundberg, "Generalized Viterbi Algorithms for Error Detection with Convolutional Codes," Conf. Rec. IEEE GLOBECOM '89, 1534-1538, Dallas, Tex., November 1989; W. C. Wong, N. Seshadri and C-E. W. Sundberg, "Estimating Unreliable Packets in Subband Coded Speech," Conf. Rec. IEEE GLOBECOM '90, 1979-1983, San Diego, Calif., December 1990.
A block diagram of a prior art communication system employing a concatenated coding architecture is shown in FIG. 3. In this system, the information source 20 generates either analog or discrete information. Outer encoder 21 transforms the signal from information source 20 into a sequence of information bits and encodes the sequence. Interleaver 22 serves to distribute the channel impairments, such as fading or noise bursts, over a plurality of blocks thus lessening the effect of the impairment on any single block. An interleaver may be considered an element for processing signals using a rectangular array. Encoded data is read into the array by rows and is read out by columns. Inner encoder 23 encodes the sequence output by interleaver 22 and also generates the modulation signal which will be transmitted over channel 24. Inner decoder 25 demodulates the received signal and performs the first step in the decoding process. Deinterleaver 26 reorders the output sequence from the inner decoder. Outer decoder 27 transforms the deinterleaved sequence into an estimate of the original information sequence and transmits the estimate to destination 28.
Since 1967, several publications have appeared extending the classical VA by adding parallel or serial processing units to the Viterbi decoder. In these units information lost due to selecting only the path with the best metric is taken into account, and additional information is delivered to an outer stage of processing. There are two general groups of extended Viterbi algorithm processors: the first group, known as soft symbol output Viterbi algorithms, uses the difference between the accumulated metrics of the two paths merging at each state as measure of the reliability of the transmitted information sequence. The second group, known as list or general output algorithms, in addition to finding the best path or survivor, computes the best next L-1 paths.
The first group of processors was introduced in 1971 by Clark and Davis who described an extended Viterbi Algorithm that delivered, in addition to the decoded information sequence, a two-valued reliability indicator L, where L.epsilon.{0,1}. G. Clark & R. Davis, "Two Recent Applications of Error-Correction Coding to Communications System Design," IEEE Trans. Comm., Vol. COM-19, No. 5, 856-863 (October 1971). Based on the earlier work of Forney, see G. D. Forney, "The Viterbi Algorithm," Proc. of IEEE, Vol. 61, No. 3, 268-278, (March 1973), Schaub and Modestino introduced an Erasure Declaring Viterbi decoding Algorithm (EDVA), which calculates, for all the merging paths at one state, the difference between their metric and the metric of the survivor path. If this difference was lower than a defined threshold, all the positions in the survivor path in which the two paths differ were erased. T. Schaub & J. W. Modestino, "An Erasure Decoding Viterbi Decoder and Its Application to Concatenated Coding System," ICC'86, IEEE Conf. Rec. No. CH 2314-3/186, 1612-1616, 1986.
Hagenauer and Hoeher have developed the Soft-Output Viterbi Algorithm (SOVA). See J. Hagenauer and P. Hoeher, "Concatenated Viterbi-Decoding," Fourth Joint Swedish-Soviet Int. Workshop on Inf. Theory, Gotland, Sweden, Studentlitteratur, Lund, 29-33 (August 1989). This algorithm delivers, for each decoded information bit, an analog reliability value L, where L.epsilon.R.sup.+. For every survivor path x(s.sub.i) a reliability vector L(s.sub.i) exists, which is initialized in all positions to a high value. At every time instant i and at any state s.sub.i, the absolute difference, .DELTA..sub.i (s.sub.i), between the accumulated metrics of the two paths merging at this point is computed. The absolute difference, .DELTA..sub.i (s.sub.i), is stored in all those positions of the reliability vector, L.sub.i (s.sub.i), where the two paths within a chosen update window .delta..sub.up differ, and where the existing reliability value, L.sub.i (s.sub.i), is higher than .DELTA..sub.i (s.sub.i) (min{.DELTA..sub.i (s.sub.i),L.sub.i (s.sub.i)}.fwdarw.L.sub.i (s.sub.i)). This updating process guarantees that, for every decoded information bit, x.sub.i, the lowest reliability value, L.sub.i, is delivered to an outer stage of processing. It is important to note that the SOVA always requires interleaving and deinterleaving units to avoid correlation of the output bits.
The second group of processors, known as List output Viterbi Algorithms (LVA), or Generalized Viterbi Algorithms (GVA), were first introduced in 1973 by Forney, supra, who proposed altering the VA to produce the L best paths rather than the single best path. In 1987 Hashimoto introduced the Generalized Viterbi Algorithm (GVA) which selects the L best survivors from each of the lists of candidates at each decoding step. T. Hashimoto, "A List-Type Reduced-Constraint Generalization of the Viterbi Algorithm," IEEE Trans. Info. Theory, Vol. IT-33, No. 6, 866-876 (November 1986).
Seshadri and Sundberg have presented versions of the GVA that produce a rank ordered list of the L globally best candidate paths after a trellis search. In a parallel version (PGVA), L survivors are selected simultaneously at each decoding step out of a list of 2.multidot.L candidates (assuming a binary code). These L survivors are then extended in the next decoding step. After the block is transmitted, an outer decoder chooses the optimal candidate from the list of the L survivors. Another version, the Serial Generalized Viterbi Algorithm (SGVA), iteratively finds the l.sup.th best path based on the knowledge of the previously found (l-1) best paths, where 1&lt;l.ltoreq.L. An application for a patent on this invention was granted to Seshadri and Sundberg on May 4, 1993, U.S. Pat. No. 5,208,816 and is assigned to the assignee of this application. Recently the more precise name List output Viterbi Algorithm (LVA) has been used in referring to the GVA. Here the more general name "GVA" is used as cited in the literature.
Both the SOVA and GVA extensions of the Viterbi algorithm improve decoding performance. However, use of the SOVA and GVA add additional complexity and cost to decoding systems.